package mess;

import com.sun.corba.se.spi.legacy.connection.LegacyServerSocketManager;

import java.util.Arrays;

public class LeeCode_57 {
    public static void main(String[] args) {
        int[][] nums = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newIn = new int[]{4, 8};
        int[][] nums1 = new int[][]{{1, 5}};
        int[] newIn1 = new int[]{0,0};
        int[][] nums2 = new int[][]{{3, 5},{12,15}};
        int[] newIn2 = new int[]{6, 6};

        int[][] res = insert(nums2, newIn2);
        for (int[] re : res) {
            System.out.print(Arrays.toString(re));
        }
    }

    private static int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        if (len == 0) {
            int[][] res = new int[1][2];
            res[0] = newInterval;
            return res;
        }
        int left = newInterval[0];
        int right = newInterval[1];
        int start = -1;
        int end = -1;
        for (int i = 0; i < len; i++) {
            if (intervals[i][0] >= left || intervals[i][1] >= left) {
                start = i;
                break;
            }
        }
        if (start == -1) {
            int[][] res = new int[len + 1][2];
            for (int i = 0; i < intervals.length; i++) {
                res[i] = intervals[i];
            }
            res[len] = newInterval;
            return res;
        }

        int max = Math.max(intervals[start][1], newInterval[1]);
        for (int i = start; i < len; i++) {
            max = Math.max(max, intervals[i][1]);
            if (intervals[i][0] > right) {
                end = i - 1;
                break;
            } else if (intervals[i][1] >= right) {
                end = i;
                break;
            }
        }

        if (start > end && end != -1){
            int[][] res = new int[len + 1][2];
            for (int i = 0; i < start; i++) {
                res[i] = intervals[i];
            }
            res[start] = newInterval;
            for (int i = start + 1; i < len + 1; i++) {
                res[i] = intervals[i - 1];
            }
            return res;
        }

        if (start == 0 && newInterval[1] < intervals[0][0] && right < intervals[start][0]) {
            int[][] res = new int[len + 1][2];
            for (int i = 0; i < intervals.length; i++) {
                res[i + 1] = intervals[i];
            }
            res[0] = newInterval;
            return res;
        }

        int[] in = new int[2];
        in[0] = Math.min(intervals[start][0], newInterval[0]);
        in[1] = end != -1 ? Math.max(intervals[end][1],newInterval[1]) : max;

        int[][] res = new int[end != -1 ? len - end + start : start + 1][2];
        for (int i = 0, j = 0; i < len; i++) {
            if (j > res.length - 1)
                continue;
            if (i > start && i <= end)
                continue;
            if (i == start) {
                res[j] = in;
                j++;
                continue;
            }
            res[j] = intervals[i];
            j++;
        }
        return res;
    }
}
